package com.yiwenup.struct._05_unionfind;

/**
 * 并查集：快速查找实现
 * 基于 rank 的优化，避免可能出现退化到链表结构的情况：合并的时候，【矮】的树，挂到【高】的树上
 * <p>
 * 时间复杂度：find - O(logn)；union - O(logn)
 **/
public class QuickUnionV3 extends QuickUnionV1 {

    /**
     * 保存每个元素，以它作为更节点的树的节点个数
     */
    private final int[] ranks;

    public QuickUnionV3(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        for (int i = 0; i < parents.length; i++) {
            ranks[i] = 1;
        }
    }

    /**
     * 基于 rank 的优化
     * 将 {@param v1} 所在集合的根节点设置为  {@param v2} 的根节点
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        if (ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else {
            // 高度一样的两棵树，嫁接方向无所谓，重要的是高度要 +1
            parents[p1] = p2;
            ranks[p2]++;
        }
    }
}
